package com.example.summary.erFenChaZhao;

/**
 * Created by wzn on 2019/4/11.
 */
public class Efcz {

    public static void main(String[] args) {
//        int[] nums = new int[]{1, 3, 5, 7, 9, 11, 13};
//        System.out.println(efSearchNew(nums, 11, 0, nums.length - 1));
////
//        int[] numsFirst = new int[]{1, 3, 3, 5, 5, 5, 7, 9, 11, 11, 13};
//        System.out.println(efSearchFirstNew(numsFirst, 11, 0, numsFirst.length - 1));
////
//        int[] numsLast = new int[]{1, 3, 3, 5, 5, 5, 7, 9, 11, 11, 13, 14};
//        System.out.println(efSearchLastNew(numsLast, 5, 0, numsLast.length - 1));
////
//        int[] numsFirstBigE = new int[]{1, 3, 3, 5, 5, 5, 7, 9, 11, 11, 13, 14};
//        System.out.println(efSearchFirstBigEN(numsFirstBigE, 8, 0, numsLast.length - 1));
////
//        int[] numsLastL = new int[]{1, 3, 3, 5, 5, 5, 7, 9, 11, 11, 13, 14};
//        System.out.println(efSearchLastLN(numsLastL, 12, 0, numsLast.length - 1));

        int[] numsXunHuan = new int[]{4, 5, 6, 7,8, 0, 1, 2 };
        System.out.println(efSearchXunHuan(numsXunHuan, 2, 0, numsXunHuan.length - 1));

//        System.out.println(mySqrt(1));
    }

    /**
     * 简单二分
     *
     * @param nums
     * @param target
     * @param low
     * @param high
     * @return
     */
    private static int efSearch(int[] nums, int target, int low, int high) {
        if (low <= high) {
            int zhongDian = low + (high - low) / 2;

            if (nums[zhongDian] > target) {
                return efSearch(nums, target, low, zhongDian - 1);
            }

            if (nums[zhongDian] < target) {
                return efSearch(nums, target, zhongDian + 1, high);
            }

            return zhongDian;
        }
        return -1;
    }

    private static int efSearchNew(int[] nums, int target, int low, int high) {

        while (low <= high) {
            int mid = low + (high - low) / 2;

            if (nums[mid] > target) {
                return efSearchNew(nums, target, low, mid - 1);
            }

            if (nums[mid] < target) {
                return efSearchNew(nums, target, mid + 1, high);
            }

            return mid;
        }

        return -1;
    }

    /**
     * 查找第一个等于给定值的元素
     */
    private static int efSearchFirst(int[] nums, int target, int low, int high) {
        if (low <= high) {
            int zhongDian = low + (high - low) / 2;

            if (nums[zhongDian] > target) {
                return efSearchFirst(nums, target, low, zhongDian - 1);
            }

            if (nums[zhongDian] < target) {
                return efSearchFirst(nums, target, zhongDian + 1, high);
            }

            if (zhongDian == 0 || nums[zhongDian - 1] != target) {
                return zhongDian;
            } else {
                return efSearchFirst(nums, target, low, zhongDian - 1);
            }
        }
        return -1;
    }

    private static int efSearchFirstNew(int[] nums, int target, int low, int high) {
        while (low <= high) {
            int mid = low + (high - low) / 2;

            if (nums[mid] > target) {
                return efSearchFirstNew(nums, target, low, mid - 1);
            }

            if (nums[mid] < target) {
                return efSearchFirstNew(nums, target, mid + 1, high);
            }

            if (mid != 0 && nums[mid - 1] == target) {
                return efSearchFirstNew(nums, target, low, mid - 1);
            }

            return mid;

        }

        return -1;
    }

    /**
     * 查找最后一个等于给定值的元素
     */
    private static int efSearchLast(int[] nums, int target, int low, int high) {
        if (low <= high) {
            int zhongDian = low + (high - low) / 2;

            if (nums[zhongDian] > target) {
                return efSearchLast(nums, target, low, zhongDian - 1);
            }

            if (nums[zhongDian] < target) {
                return efSearchLast(nums, target, zhongDian + 1, high);
            }

            if (zhongDian == high || nums[zhongDian + 1] != target) {
                return zhongDian;
            } else {
                return efSearchLast(nums, target, zhongDian + 1, high);
            }
        }
        return -1;
    }


    private static int efSearchLastNew(int[] nums, int target, int low, int high) {
        while (low <= high) {
            int mid = low + (high - low) / 2;

            if (nums[mid] > target) {
                return efSearchLastNew(nums, target, low, mid - 1);
            }

            if (nums[mid] < target) {
                return efSearchLastNew(nums, target, mid + 1, high);
            }

            if (mid != high && nums[mid + 1] == target) {
                return efSearchLastNew(nums, target, mid + 1, high);
            }

            return mid;
        }

        return -1;
    }

    /**
     * 查找第一个大于等于的
     *
     * @return
     */
    private static int efSearchFirstBigE(int[] nums, int target, int low, int high) {
        if (low <= high) {
            int zhongDian = low + (high - low) / 2;

            if (nums[zhongDian] >= target) {
                if (zhongDian == 0 || nums[zhongDian - 1] < target) {
                    return zhongDian;
                }
                return efSearchFirstBigE(nums, target, low, zhongDian - 1);
            }

            if (nums[zhongDian] < target) {
                return efSearchFirstBigE(nums, target, zhongDian + 1, high);
            }

        }
        return -1;
    }

    private static int efSearchFirstBigEN(int[] nums, int target, int low, int high) {

        while (low <= high) {
            int mid = low + (high - low) / 2;

            if (nums[mid] >= target) {
                if (mid == low || nums[mid - 1] < target) {
                    return mid;
                }
                return efSearchFirstBigEN(nums, target, low, mid - 1);
            }

            if (nums[mid] < target) {
                return efSearchFirstBigEN(nums, target, mid + 1, high);
            }

        }

        return -1;

    }

    /**
     * 查找最后一个小于等于给定值
     *
     * @param nums
     * @param target
     * @param low
     * @param high
     * @return
     */
    private static int efSearchLastL(int[] nums, int target, int low, int high) {
        if (low <= high) {
            int zhongdian = low + (high - low) / 2;

            if (nums[zhongdian] > target) {
                return efSearchLastL(nums, target, low, zhongdian - 1);
            }

            if (nums[zhongdian] <= target) {

                if (zhongdian == high || nums[zhongdian + 1] > target) {
                    return zhongdian;
                }
                return efSearchLastL(nums, target, zhongdian + 1, high);
            }
        }
        return -1;
    }

    private static int efSearchLastLN(int[] nums, int target, int low, int high) {
        while (low <= high) {
            int mid = low + (high - low) / 2;

            if (nums[mid] <= target) {
                if (mid == high || nums[mid + 1] > target) {
                    return mid;
                }

                return efSearchLastLN(nums, target, mid + 1, high);
            }

            if (nums[mid] > target) {
                return efSearchLastLN(nums, target, low, mid - 1);
            }
        }

        return -1;
    }


    /**
     * 循环集合找
     *
     * @param nums
     * @param target
     * @param low
     * @param high
     * @retun 4, 5, 6, 7,8, 0, 1, 2   4567 8012
     * 6,7,8,0,1,2,3,4,5 6780 1234
     */
    private static int efSearchXunHuan(int[] nums, int target, int low, int high) {
        if (low <= high) {

            int mid = low + (high - low) / 2;
            if (nums[mid] == target) {
                return mid;
            }

            /**
             * 前区有序，否则后区有序
             */
            if (nums[low] <= nums[mid]) {
                /**
                 * 前区有序
                 */
                if (target >= nums[low] && target <= nums[nums[low] == nums[mid] ? mid : mid - 1]) {
                    return efSearchXunHuan(nums, target, low, nums[low] == nums[mid] ? mid : mid - 1);
                } else {
                    return efSearchXunHuan(nums, target, mid + 1, high);
                }
            }

            if (nums[low] > nums[mid]) {
                /**
                 * 后区有序
                 */
                if (target >= nums[mid + 1] && target <= nums[high]) {
                    return efSearchXunHuan(nums, target, mid + 1, high);
                } else {
                    return efSearchXunHuan(nums, target, low, mid - 1);
                }
            }

        }

        return -1;
    }


    public static int mySqrt(int x) {
        return sqrt(0, x, x);
    }

    public static int sqrt(long low, long max, int x) {
        long mid = low + (max - low) / 2;

        if (mid * mid < x) {
            if ((mid + 1) * (mid + 1) <= x) {
                return sqrt(mid + 1, max, x);
            }
            return (int) mid;
        }

        if (mid * mid > x) {
            if ((mid - 1) * (mid - 1) > x) {
                return sqrt(0, mid - 1, x);
            }
            return (int) (mid - 1);
        }

        return (int) mid;
    }
}
